package com.lw.leetcode.add.e;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * 1632. 矩阵转换后的秩
 *
 * @author liw
 * @version 1.0
 * @date 2022/10/28 9:44
 */
public class MatrixRankTransform {

    public static void main(String[] args) {
        MatrixRankTransform test = new MatrixRankTransform();

        // {{1,2},{2,3}}
        int[][] matrix = {{1, 2}, {3, 4}};

        // {{1,1},{1,1}}
//        int[][] matrix = {{7, 7}, {7, 7}};

        // {{4,2,3},{1,3,4},{5,1,6},{1,3,4}}
//        int[][] matrix = {{20, -21, 14}, {-19, 4, 19}, {22, -47, 24}, {-19, 4, 19}};

        // {{5,1,4},{1,2,3},{6,3,1}}
//        int[][] matrix = {{7, 3, 6}, {1, 4, 5}, {9, 8, 2}};

        //
//        int[][] matrix = Utils.getArr(300, 300, -1000000000, 1000000000);

        int[][] ints = test.matrixRankTransform(matrix);
        for (int[] anInt : ints) {
            System.out.println(Arrays.toString(anInt));
        }
    }

    private int[] vxs;
    private int[] ixs;
    private int[] vys;
    private int[] iys;
    private int[][] matrix;

    public int[][] matrixRankTransform(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int length = m * n;
        long[] arr = new long[length];
        this.matrix = matrix;
        int index = 0;
        for (int i = 0; i < m; i++) {
            int[] item = matrix[i];
            int x = i << 12;
            for (int j = 0; j < n; j++) {
                arr[index++] = (((long) item[j]) << 32) + x + j;
            }
        }
        Arrays.sort(arr);
        vxs = new int[m];
        ixs = new int[m];
        vys = new int[n];
        iys = new int[n];
        Arrays.fill(vxs, Integer.MIN_VALUE);
        Arrays.fill(vys, Integer.MIN_VALUE);
        List<Long> list = new ArrayList<>();

        for (int i = 0; i < length; i++) {
            long l = arr[i];
            list.add(l);
            if (i == length - 1) {
                find(list);
            } else {
                if (arr[i + 1] >> 32 != l >> 32) {
                    find(list);
                }
            }
        }
        return matrix;
    }

    private void find(List<Long> list) {
        int value = 0;
        for (Long l : list) {
            int v = (int) (l >> 32);
            int x = (int) ((l >> 12) & 0XFFF);
            int y = (int) (l & 0XFFF);
            int t = Math.max(v > vxs[x] ? ixs[x] + 1 : ixs[x], v > vys[y] ? iys[y] + 1 : iys[y]);
            value = Math.max(value, t);
            vxs[x] = v;
            vys[y] = v;
        }
        for (Long l : list) {
            int x = (int) ((l >> 12) & 0XFFF);
            int y = (int) (l & 0XFFF);
            ixs[x] = value;
            iys[y] = value;

            matrix[x][y] = value;
        }
        list.clear();

    }

}
